typedef int datatype;
#pragma region  【算法7 - 10】两个有序表的合并。 
void Merge(datatype R[], datatype R1[], int s, int m, int t)
{ //设两个有序子表R[s]..R[m]和R[m+1]..R[t]，
  //将两个有序子表合并为一个有序表R1[s]..R1[t]
    i = s;
    j = m + 1;
    k = s;
    while (i <= m && j <= t)
        if (R[i].key < R[j].key)
            R1[k++] = R[i++];
        else
            R1[k++] = R[j++];
    while (i <= m)
        R1[k++] = R[i++];
    while (j <= t)
        R1[k++] = R[j++];
}
#pragma endregion
#pragma region 【算法7 - 11】一趟归并算法
void MergePass(datatype R[], datatype R1[], int len, int n)
{ // len是本趟归并中有序表的长度，
  //从R[1]..R[n]归并到R1[1]..R1[n]中
    i = 1;
    for (; i + 2 * len - 1 <= n; i = i + 2 * len)
        Merge(R, R1, i, i + len - 1, i + 2 * len - 1);
    //对两个长度为len 的有序表合并
    if (i + len - 1 < n)
        Merge(R, R1, i, i + len - 1, n); //一组半的情况
    else if (i <= n)
        while (i <= n) //最后一组没有合并者
            R1[i++] = R[i++];
}
#pragma endregion
#pragma region 【算法7 - 12】2 - 路归并排序
void MergeSort(datatype R[], datatype R1[], int n)
{
    int len = 1;
    while (len < n)
    {
        MergePass(R, R1, len, n);
        len = 2 * len;
        MergePass(R1, R, len, n);
        len = 2 * len;
    }
}
#pragma endregion
#pragma region 【算法7 - 13】2 - 路归并递归算法
void MSort(datatype R[], datatype R1[], int s, int t)
{ //将R[s]…R[t]归并排序为R1[s]…R1[t]
    if (s == t)
        R1[s] = R[s];
    else
    {
        m = (s + t) / 2;        //平分*p表
        MSort(R, R1, s, m);     //递归地将R[s…m]归并为有序的R1[s…m]
        MSort(R, R1, m + 1, t); //递归地将R[m+1…t]归并为有序的R1[m+1…t]
        Merge(R1, R, s, m, t);  //将R1[s…m]和R1[m+1…t]归并到R[s…t]
    }
}
void MergeSort(datatype R[], datatype R1[], int n)
{ //对排序表R[1]..R[n]作归并排序
    MSort(R, R1, 1, n);
}
#pragma endregion